/*
ID: quxiao82
LANG: C++
PROG: inflate
*/


#include <cstdio>
#include <cstring>
#include <cstdlib>

const int MAX = 10001;

struct Problem
{
       int len, point;
};

int m, n;
Problem p[MAX];
int maxPoint[MAX];

void Input ()
{
       int i;
       scanf( "%d%d", &m, &n);
       for ( i = 0; i < n; i ++)
             scanf( "%d%d", &p[i].point, &p[i].len);
}

void Solve ()
{
       int i, j;
       for ( i = 1; i <= m; i ++)
      {
             for ( j = 0; j < n; j ++)
            {
                   if ( i - p[ j]. len >= 0 && maxPoint[ i] < maxPoint[i-p[j].len] + p[j].point )
                  {
                         maxPoint[ i] = maxPoint[ i- p[ j]. len] + p[ j]. point;
                  }
            }
      }
       printf( "%d\n", maxPoint[m]);
}

int main ()
{
       freopen( "inflate.in", "r" , stdin );
       freopen( "inflate.out", "w" , stdout );

       Input();
       Solve();

       return 0;
}
